10149 - Yahtzee/10149.cpp

   1 /*
   2   Backtracking. Infinitely slow.
   3  */
   4 using namespace std;
   5 #include <algorithm>
   6 #include <iostream>
   7 #include <iterator>
   8 #include <sstream>
   9 #include <fstream>
  10 #include <numeric>
  11 #include <cassert>
  12 #include <climits>
  13 #include <cstdlib>
  14 #include <cstring>
  15 #include <string>
  16 #include <cstdio>
  17 #include <vector>
  18 #include <cmath>
  19 #include <queue>
  20 #include <deque>
  21 #include <stack>
  22 #include <list>
  23 #include <map>
  24 #include <set>
  25
  26 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  27 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  28 #define D(x) cout << #x " is " << x << endl
  29
  30 typedef int turn[5];
  31
  32 enum category {
  33   ones, twos, threes, fours, fives, sixes, chance, three_of_a_kind,
  34   four_of_a_kind, five_of_a_kind, short_straight, long_straight,
  35   full_house
  36 };
  37
  38 int score(turn t, int c){
  39   int times[7] = {0};
  40   for (int i=0; i<6; ++i) times[t[i]]++;
  41   switch(c){
  42   case ones:
  43     return times[1] * 1;
  44   case twos:
  45     return times[2] * 2;
  46   case threes:
  47     return times[3] * 3;
  48   case fours:
  49     return times[4] * 4;
  50   case fives:
  51     return times[5] * 5;
  52   case sixes:
  53     return times[6] * 6;
  54   case chance:
  55     return accumulate(t, t+5, 0);
  56   case three_of_a_kind:
  57     for (int i=1; i<=6; ++i) if (times[i] >= 3) return accumulate(t, t+5, 0);
  58     return 0;
  59   case four_of_a_kind:
  60     for (int i=1; i<=6; ++i) if (times[i] >= 4) return accumulate(t, t+5, 0);
  61     return 0;
  62   case five_of_a_kind:
  63     for (int i=1; i<=6; ++i) if (times[i] >= 5) return 50;
  64     return 0;
  65   case short_straight:
  66     for (int i=1; i<=3; ++i)
  67       if (times[i] > 0  && times[i+1] > 0 && times[i+2] > 0 && times[i+3] > 0) return 25;
  68     return 0;
  69   case long_straight:
  70     for (int i=1; i<=2; ++i)
  71       if (times[i] > 0  && times[i+1] > 0 && times[i+2] > 0 && times[i+3] > 0 && times[i+4] > 0) return 35;
  72     return 0;
  73
  74   case full_house:
  75     for (int i=1; i<=6; ++i)
  76       for (int j=1; j<=6; ++j)
  77         if (times[i] == 3 && times[j] == 2) return 40;
  78     return 0;
  79   default:
  80     printf("Something very bad happened.\n");
  81   }
  82   return 0;
  83 }
  84
  85 turn turns[13];
  86
  87 int bonus;
  88 int best_score;
  89 int best_match[13]; //best_match[i] = Turn matched with category i
  90 int current_match[13];
  91
  92 void backtrack(int i, int used_categories, int current_score){
  93   if (i == 13){
  94     int sum = 0;
  95     for (int c=ones; c<=sixes; ++c) sum += score(turns[best_match[c]], c);
  96     int current_bonus = 0;
  97     if (sum >= 63){
  98       current_score += (current_bonus = 35); //bonus
  99     }
 100     printf("Found a matching of %d:\n", current_score);
 101     for (int c=ones; c<=full_house; ++c){
 102       printf("%d ", current_match[c]);
 103     }
 104     printf("\n");
 105
 106     if (current_score > best_score){
 107       best_score = current_score;
 108       bonus = current_bonus;
 109       memcpy(best_match, current_match, sizeof best_match);
 110     }
 111     return;
 112   }
 113
 114   for (int c=ones; c<=full_house; ++c){
 115     if (!(used_categories & (1 << c))){
 116       current_match[c] = i;
 117       backtrack(i + 1, used_categories | (1 << c), current_score + score(turns[i], c));
 118       current_match[c] = -1;
 119     }
 120   }
 121 }
 122
 123
 124 int main(){
 125   while (true){
 126     for (int i=0; i<13; ++i){
 127       for (int j=0; j<5; ++j){
 128         if (scanf("%d", &turns[i][j]) != 1) return 0;
 129       }
 130     }
 131
 132     best_score = 0;
 133     backtrack(0, 0, 0);
 134
 135     for (int c=ones; c<=full_house; ++c){
 136       printf("%d ", best_match[c]);
 137       printf("%d %d\n", bonus, best_score);
 138     }
 139
 140   }
 141   return 0;
 142 }